UVa/11656 - Message in the Enemy Territory/11656.cpp

   1 // Wrong Answer
   2 // Just to make sure the input is well formed and there are no three
   3 // consecutive collineal points in the border of the resulting polygon.
   4 using namespace std;
   5 #include <algorithm>
   6 #include <iostream>
   7 #include <iterator>
   8 #include <numeric>
   9 #include <sstream>
  10 #include <fstream>
  11 #include <cassert>
  12 #include <climits>
  13 #include <cstdlib>
  14 #include <cstring>
  15 #include <string>
  16 #include <cstdio>
  17 #include <vector>
  18 #include <cmath>
  19 #include <queue>
  20 #include <deque>
  21 #include <stack>
  22 #include <list>
  23 #include <map>
  24 #include <set>
  25
  26 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define D(x) cout << #x " is " << x << endl
  29
  30 const int MAXC = 1035;
  31
  32 typedef pair< int, int > point;
  33 typedef pair< point, point > side;
  34
  35 vector< int > YgivenX[MAXC], XgivenY[MAXC];
  36 vector< side > sides;
  37
  38 bool isSimpleClosedPolygon() {
  39     point start = sides[0].first;
  40
  41     set<point> seen;
  42     point cur = start;
  43
  44     do {
  45         seen.insert(cur);
  46         point next;
  47
  48         printf("Inserted <%d, %d>\n", cur.first, cur.second);
  49         for (int i = 0; i < sides.size(); ++i) {
  50             if (sides[i].first == cur or sides[i].second == cur) {
  51                 next = sides[i].first == cur ? sides[i].second : sides[i].first;
  52                 assert(next != cur);
  53                 if (seen.count(next) == 0) {
  54                     break;
  55                 }
  56             }
  57         }
  58         printf("next = <%d, %d>\n", next.first, next.second);
  59         cur = next;
  60     } while (cur != start);
  61
  62     return seen.size() == sides.size();
  63 }
  64
  65 int main(){
  66     int n, m;
  67     while (cin >> n >> m) {
  68         if (n == 0 and m == 0) break;
  69
  70         assert(n % 2 == 0);
  71
  72         For(i, 0, MAXC) YgivenX[i].clear(), XgivenY[i].clear();
  73
  74         For(i, 0, n) {
  75             int x, y; cin >> x >> y;
  76             XgivenY[y].push_back( x );
  77             YgivenX[x].push_back( y );
  78         }
  79         int x1, y1, x2, y2;
  80         cin >> x1 >> y1 >> x2 >> y2;
  81
  82         sides.clear();
  83
  84         For(x, 0, MAXC) {
  85             sort(YgivenX[x].begin(), YgivenX[x].end());
  86             assert(YgivenX[x].size() % 2 == 0);
  87             for (int k = 0; k < YgivenX[x].size(); k += 2) {
  88                 int y = YgivenX[x][k];
  89                 int nextY = YgivenX[x][k+1];
  90
  91                 sides.push_back(  side(point(x, y), point(x, nextY))  );
  92             }
  93         }
  94
  95         For(y, 0, MAXC) {
  96             sort(XgivenY[y].begin(), XgivenY[y].end());
  97             assert(XgivenY[y].size() % 2 == 0);
  98             for (int k = 0; k < XgivenY[y].size(); k += 2) {
  99                 int x = XgivenY[y][k];
 100                 int nextX = XgivenY[y][k+1];
 101
 102                 sides.push_back(  side(point(x, y), point(nextX, y))  );
 103             }
 104         }
 105
 106         assert(sides.size() == n);
 107         for (int i = 0; i < sides.size(); ++i) {
 108             printf("There's a side from <%d, %d> to <%d, %d>\n", sides[i].first.first, sides[i].first.second, sides[i].second.first, sides[i].second.second);
 109         }
 110         assert(isSimpleClosedPolygon());
 111         puts("NO");
 112     }
 113     return 0;
 114 }